package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-15 13:56
 **/
public class LeetCode287 {

    /**
     * hash表法
     * @param nums
     * @return
     */
    /*public int findDuplicate(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return nums[i];
            }
            map.put(nums[i],i);
        }
        return -1;
    }*/

    /**
     * 快慢指针法
     * @param nums
     * @return
     */
    public static int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }



    public static void main(String[] args) {
        System.out.println(findDuplicate(new int[]{3,4,2,0,0,1}));
    }
}
